package m202311.d06;

/**
 * @author haocongshun
 * @date 2023/11/06 19:30:08
 */

import java.util.List;

/**
 * 45. 跳跃游戏 II
 */
public class Q45 {
    public static void main(String[] args) {
        int jump = new Q45().jump(new int[]{1, 2, 3, 4});
        System.out.println(jump);
    }

    public int jump(int[] nums) {
        return jump(nums, nums.length - 1);
    }

    public int jump(int[] nums, int index) {
        if (index == 0) {
            return 0;
        }
        if (nums[0] >= index) {
            return 1;
        }
        int minIndex = index - 1;
        for (int i = index - 1; i >= 0; i--) {
            if (nums[i] >= index - i) {
                minIndex = i;
            }
        }
        return 1 + jump(nums, minIndex);
    }

}
